public class 数组中两个数的最大异或值 {
    public static int MAXN = 300000;
    public static int[][] tree = new int[MAXN][2];
    public static int high;
    public static int cnt;
    public int findMaximumXOR(int[] nums) {
        build(nums);
        int ans = 0;
        for (int num : nums) {
            ans = Math.max(ans,maxXor(num));
        }
        return ans;
    }

    private int maxXor(int num) {
        int cur = 1;
        int ans = 0;
        for (int i = high; i >= 0; i--) {
            int status = (num >> i) & 1;
            int want = 1 ^ status;
            if (tree[cur][want] == 0) {
                want ^= 1;
            }
            ans |= (want ^ status) << i;
            cur = tree[cur][want];
        }
        return ans;
    }


    public static void build (int[] nums) {
        cnt = 1;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            max = Math.max(num,max);
        }
        high = 31 - Integer.numberOfLeadingZeros(max);
        for (int num : nums) {
            insert(num);
        }
    }

    public static void insert (int num) {
        int cur = 1;
        for (int i = high; i >= 0; i--) {
            int path = (num >> i) & 1;
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
        }
    }


}
